package algorithms.question.class14;

import common.util.MyUtil;

/**
 * 给定一个只由左括号和右括号的字符串
 * 返回最长的有效括号子串的长度
 *
 * @author guichang
 * @date 2021/8/11
 */

@SuppressWarnings("all")
public class Code1_有效括号子串的长度 {

    public static void main(String[] args) {
        String str = "())";
        MyUtil.print(longestValidParentheses(str));
    }

    public static int longestValidParentheses(String str) {
        if (str == null || str.length() < 2) {
            return 0;
        }
        char[] strs = str.toCharArray();
        // dp含义：以i位置结尾的字串最长的有效长度为dp[i]
        int[] dp = new int[strs.length];
        int res = 0;
        for (int i = 1; i < strs.length; i++) {
            // 左括号直接0
            if (strs[i] == '(') {
                continue;
            }
            int imax = 0;
            // 左边有有效值
            int p1 = i - dp[i - 1] - 1;
            if (p1 < 0) {
                continue;
            }
            char oneLeft = strs[p1];
            if (oneLeft == ')') {
                continue;
            }
            imax = dp[i - 1] + 2;
            // 有没有往前延申的可能
            int p2 = p1 - 1;
            if (p2 >= 0) {
                imax += dp[p2];
            }
            dp[i] = imax;
            res = Math.max(res, imax);
        }
        return res;
    }
}